package org.example.myleet.p1305;

import org.example.myleet.Utils.TreeNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {

    /**
     * 中序+归并
     */
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> numbers1 = new ArrayList<>();
        if (null != root1) {
            traverse(root1, numbers1);
        }
        List<Integer> numbers2 = new ArrayList<>();
        if (null != root2) {
            traverse(root2, numbers2);
        }
        if (0 == numbers1.size()) {
            return numbers2;
        }
        if (0 == numbers2.size()) {
            return numbers1;
        }
        int i1 = 0, i2 = 0;
        List<Integer> numbers = new ArrayList<>(numbers1.size() + numbers2.size());
        while (i1 < numbers1.size() || i2 < numbers2.size()) {
            if (i1 >= numbers1.size()) {
                numbers.add(numbers2.get(i2));
                ++i2;
                continue;
            }
            if (i2 >= numbers2.size()) {
                numbers.add(numbers1.get(i1));
                ++i1;
                continue;
            }
            int num1 = numbers1.get(i1);
            int num2 = numbers2.get(i2);
            if (num1 <= num2) {
                numbers.add(num1);
                ++i1;
            } else {
                numbers.add(num2);
                ++i2;
            }
        }
        return numbers;
    }

    /**
     * 中序+排序
     */
//    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
//        List<Integer> numbers = new ArrayList<>();
//        if (null != root1) {
//            traverse(root1, numbers);
//        }
//        if (null != root2) {
//            traverse(root2, numbers);
//        }
//        numbers.sort(Comparator.naturalOrder());
//        return numbers;
//    }

    private void traverse(TreeNode node, List<Integer> numbers) {
        if (null == node.left && null == node.right) {
            numbers.add(node.val);
            return;
        }
        if (null != node.left) {
            traverse(node.left, numbers);
        }
        numbers.add(node.val);
        if (null != node.right) {
            traverse(node.right, numbers);
        }
    }
}
